// https://www.lintcode.com/problem/sentence-similarity/

public class Solution {
    /**
     * @param words1: a list of string
     * @param words2: a list of string
     * @param pairs: a list of string pairs
     * @return: return a boolean, denote whether two sentences are similar or not
     */
    public boolean isSentenceSimilarity(String[] words1, String[] words2, List<List<String>> pairs) {
        // write your code here
        if (words1.length == words2.length) {
            HashSet<String> set = new HashSet<>();
            for (int i = 0; i < pairs.size(); ++i) {
                List<String> pair = pairs.get(i);
                set.add(pair.get(0) + pair.get(1));
                set.add(pair.get(1) + pair.get(0));
            }
            for (int i = 0; i < words1.length; ++i) {
                String w1 = words1[i];
                String w2 = words2[i];
                if ((!w1.equals(w2)) && (!set.contains(w1 + w2))) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
}